
// left: 维护的是左边比栈顶元素小的第一个元素的下标
// right: 维护的是右边比栈顶元素小的第一个元素的下标
// stack: 栈不为空时，栈顶元素和当前元素比较 遍历数组，然后当前元素小于等于栈顶元素就入栈，栈顶元素left是左边第一个比它小的元素下标
// 当前元素比栈顶元素大时，说明找到了右边第一个比栈顶元素小的元素下标，计算差值更新结果数组
// 当前元素比栈顶元素小或等于时，那么当前元素的左边第一个比它小的元素下标就是栈顶元素下标 然后入栈
#include <vector>
#include <stack>
using namespace std;
class Solution
{
public:
    int largestRectangleArea(vector<int> &heights)
    {
        int n = heights.size();
        vector<int> left(n, -1);
        vector<int> right(n, n);
        stack<int> st;
        for (int i = 0; i < n; ++i)
        {
            // 1. 处理右边界
            while (!st.empty() && heights[i] < heights[st.top()])
            {
                // 当前元素  < 栈顶元素   那么就是栈顶元素右边界就是当前元素
                int index = st.top();
                st.pop();
                right[index] = i;
            }
            // 2. 处理左边界: 上面处理完之后： 要么栈为空，要么当前元素 >= 栈顶元素
            if (!st.empty())
            {
                left[i] = st.top();
            }
            // 3. 当前元素入栈
            st.push(i);
        }
        int maxArea = 0;
        for (int i = 0; i < n; ++i)
        {
            int width = right[i] - left[i] - 1;
            int area = width * heights[i];
            maxArea = max(area, maxArea);
        }
        return maxArea;
    }
};